1. Field of the Invention
The present invention relates to image processing. More specifically, the present invention relates to methods for decoding compressed image data.
While the present invention is described herein with reference to illustrative embodiments for particular applications, it should be understood that the invention is not limited thereto. Those having ordinary skill in the art and access to the teachings provided herein will recognize additional modifications, applications and embodiments within the scope thereof and additional fields in which the present invention would be of significant utility.
2. Description of the Related Art
Image data compression techniques encode image data and provide a compressed image which requires less memory for storage and has a lower transmission bandwidth than the original image. Thus, the compressed image can be transmitted or stored more easily. Generally, an image that has been compressed must be decoded to bring back the original image before the image is usable.
The most common method for encoding data for compression is transform coding. With this encoding method, the data is transformed in a manner that weights certain coefficients more heavily than others, allowing one to discard the less influential points. Examples of this coding method are the fast Fourier transform (FFT), discrete cosine, Walsh-Hadamard and the Radon transform.
Transform coding typically suffers from several problems. The computational time for computing the transforms rises exponentially with the number of pixels in the image. For large images this can lead to high costs and slow processing which can be prohibitive, particularly if real time reconstruction is desired. A further drawback is that most transforms work best over square or rectangular regions. If the image data is not presented in one of the prescribed geometries, it must be padded with zeros to make it conform, but zeros do not lower the computational complexity. Further, many conventional transform methods do not provide enough compression to be useful in certain memory intensive applications. In addition, some of these transform methods do not provide an accurate compressed image.
Compression of image data by encoding techniques is useful in various applications. For example, high definition television (HDTV) systems require a much higher bandwidth than the current American television system (which uses the NTSC standard). Proposed methods for implementing an HDTV system generally include some form of image compression to reduce the bandwidth requirements. Satellite systems are another area where image data compression is useful. Because of the expense of satellites and the limited number of satellites available for use, image data compression is important for its reduction in the burden on satellite systems. Image data compression is also useful in flight simulation systems to help reduce the typically large memory requirements. HDTV systems, satellites and flight simulators typically require fast data compression algorithms because the systems must operate near real time. Thus, even where current transform methods provide enough accuracy and compression, these methods generally do not operate quickly enough for use with conventional hardware.
Local operators such as run length encoding and quantization, unlike current transform methods, generally operate quickly enough for the above applications. However, local operators generally do not provide the required compression ratios.
The Poisson picture processing (PPP) algorithm was developed by Hughes Aircraft to alleviate the above problems. The PPP algorithm supplies fast data compression with good compression ratios and accurate reconstructions. See the final report on ACMP DATA COMPRESSION by the Hughes Aircraft, Support Systems by J. Drummond, J. McWaid, F. Lin, and K. Dubbs, December 1985 to October 1987. The Poisson method is a local operation that simulates run length encoding in two dimensions.
While the Poisson method provides a fast data compression algorithm, no iterative hardware decompression scheme is disclosed. Many applications, especially real time applications, require the speed that can only be achieved by an iterative hardware implementation. Thus, there is a need in the art for a fast method or technique for iterative hardware decoding of an image that has been encoded using the Poisson picture processing algorithm.